1. Field of the Invention
The present invention relates to public-key cryptosystems. More specifically, the present invention relates to enhancing the security of public key cryptosystem implementations.
2. Description of the Related Art
In public-key cryptosystems, a user is given a pair of cryptographic keys—a public key and a private key. Each of these keys may have one or more values/parameters. The private key is kept secret, while the public key may be widely distributed. The keys are related mathematically, but the private key cannot be practically derived from the public key. A message encrypted with the public key can be decrypted only with the corresponding private key. Similarly, a message signed with a private key can be verified using the public key counterpart of this private key.
One of the most widely used types of public-key encryption is RSA. The main operation in RSA is modular exponentiation. For example, the exponentiation may be P=Md (mod N), wherein M is a message to be decrypted and/or signed, d is the private exponent, which is part of the private key, and N is the public modulus, which is part of the public key. N is usually the product of two large primes p and q, which are parts of the private key. If a malicious user obtains the value of d, he can impersonate the owner of the key and decipher encrypted messages. Other modular exponentations, such as Md (mod p), where p is a prime number which is also a factor of the public modulus N may also be used.
Efficent RSA implementations typically use certain exponentiation algorithms which require computing the powers of the input message in a modulus. Then, during an exponentiation phase, these powers are used as operands to the modular operations.
One common technique used in RSA is Montgomery multiplication. Montgomery multiplication includes various modular functions along with a conditional substraction step that depends on the values of the operands. This is known as an extrareduction step. Due to the presence of this extrareduction step, however, it may be possible for statistical analysis to be used to deduce the value of the exponent(s). This leaves software that utilizes RSA implementations vulnerable to attack.
What is needed is a solution that reduces this security risk.